package dmsxl.shuzu;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/6 15:55
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 */
public class array3_977 {

    public static void main(String[] args) {
        int[] nums = {-4, -1, 0, 3, 10};
        int[] res = sortedSquares(nums);
        System.out.println(Arrays.toString(res));
    }

//    先平方，再排序（本次采用选择排序）,可通过，但效果很差
    public static int[] sortedSquares1(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++){
            res[i] = nums[i]*nums[i];
        }
        for (int j = 0; j < nums.length; j++){
            for (int k = j+1; k < nums.length; k++){
                if (res[k] < res[j]){
                    int temp = res[k];
                    res[k] = res[j];
                    res[j] = temp;
                }
            }
        }
        return res;
    }

//    找到正负分解线，然后类似归并排序，时间效率较高 时间复杂度O(n),空间复杂度O(1)
    public static int[] sortedSquares2(int[] nums) {
        int n = nums.length;
        int negative = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }

        int[] ans = new int[n];
        int index = 0, i = negative, j = negative + 1;
        while (i >= 0 || j < n) {
            if (i < 0) {
                ans[index] = nums[j] * nums[j];
                ++j;
            } else if (j == n) {
                ans[index] = nums[i] * nums[i];
                --i;
            } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
                ans[index] = nums[i] * nums[i];
                --i;
            } else {
                ans[index] = nums[j] * nums[j];
                ++j;
            }
            ++index;
        }
        return ans;
    }

//    双指针,较好 时间复杂度O(n),空间复杂度O(1)
    public static int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int left = 0, right = nums.length - 1, pos = nums.length-1;
        while (left <= right){
            if (nums[left]*nums[left] <= nums[right] * nums[right]){
                res[pos] = nums[right] * nums[right];
                pos -= 1;
                right -= 1;
            }else {
                res[pos] = nums[left] * nums[left];
                pos -= 1;
                left += 1;
            }
        }
        return res;
    }
}
